The present invention relates to a system and method for accessing data from a data memory and, more particularly, to a system and method that accomplishes indirect address table look-ups in a single instruction cycle.
Data processing devices such as digital signal processors and microprocessors are key components of most electronic equipment in use today. While the tasks performed by these devices is, at times, incredibly complex, the basic operation of these devices is not. To accomplish tasks of great complexity, the devices perform a large number of relatively simple operations very quickly. For example, a typical digital signal processor (xe2x80x9cDSPxe2x80x9d) performs millions of operations each second.
The operations performed by a data processing device (referred to hereafter as a xe2x80x9cdata processorxe2x80x9d) are controlled by a series of instructions that are executed by the data processor. An instruction specifies the operation to be performed and may include parameters to be used during the associated operation. Typical instructions define operations such as adding one item of data (typically referred to as a word of data) to another word of data or moving a word of data from one location in data memory to another location.
Inasmuch as the basic operation of a data processor consists of the manipulation of data, a significant percentage of its operations involve retrieving data from and sending data to data memory. In its simplest form, a data access instruction specifies the address at which the data resides in the memory. Upon execution of this instruction, the data processor retrieves the data at the specified address.
To perform more robust tasks, the data processor may use a more complicated form of addressing referred to as xe2x80x9cindirect addressing.xe2x80x9d Indirect addressing allows programmers to specify locations of data, without knowing the physical address at which the data is actually stored. For example, in a data memory with one million data locations, one thousand contiguous data locations may be designated as a data table. The address of the first data location in the table is referred to as the xe2x80x9cbase addressxe2x80x9d of the table. Data within the table can be accessed by reference to an xe2x80x9coffsetxe2x80x9d from the base address. Thus, the first data location would be identified by offset=0, the second data location by offset=1, and so forth.
To perform an indirect address data memory access, the data processor combines the offset and the base address. Typically, this involves performing the operations of reading the offset from a data memory, adding the offset to the (previously obtained) base address, and accessing the data memory location specified by the combined address.
Conventional data processors require several instructions to accomplish an indirect addressing data access. For example, a DSP sold under the product name xe2x80x9cTMS320C54xxe2x80x9d by Texas Instruments requires several cycles to perform the indirect addressing operation described above. See, for example, Table 7-2 in the TMS320C54x 1995 User""s Guide. Similarly, a DSP sold under the product name xe2x80x9cDSP16xe2x80x9d by Lucent Technologies, may require five instruction cycles per table look-up access. See, for example, the bit reverse operation in the WE(copyright) DSP16 and DSP16A Application Software Library Reference Manual.
Given the relatively large number of indirect memory accesses that may be performed by these data processors, a need exists for a data processor that can more efficiently perform data accesses using indirect addressing.
The invention provides an improved table look-up/indirect addressing system and method. The invention makes use of a dual-fetch Harvard architecture for a processor to implement one full table look-up access per instruction cycle.
The dual-fetch Harvard architecture provides two data paths that can be accessed during the same clock cycle. The invention uses these two data paths to access the offset and the data, respectively.
To accomplish a full table look-up during one clock cycle, the invention accesses data using a data pipeline. That is, the offset data accessed during a previous cycle is used during the current cycle to retrieve the data from the table. During each clock cycle, the invention reads a data word from a data memory using the address calculated during the previous cycle, adds the base address of the table to the offset obtained during the previous cycle, and reads the next offset from a data memory.